import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-06-27
 * Time:14:51
 */
public class HashTable {
    class Node {
        public int Key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            Key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "Key=" + Key +
                    ", val=" + val +
                    '}';
        }
    }
        public Node[] elem;
        public int useSize;
        public static final double DEFAULT_LOAD_FACTOR=0.75;

        public HashTable() {
            this.elem = new Node[10];
            this.useSize = 0;
        }
    public void put(int key,int val){
        //1、找到key的位置
        int index=key%this.elem.length;
        //2、判断index位置是否已经有元素。
        Node cur=this.elem[index];
        while(cur!=null){
            if (cur.Key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //3、尾插法
        Node node=new Node(key, val);
        if (this.elem[index]==null){
            this.elem[index]=node;
        }else{
            cur=this.elem[index];
            while (cur.next!=null){
               cur=cur.next;
            }
            cur.next=node;
        }
        this.useSize++;
        //4、插入元素成功之后，检查当前散列表的负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    //扩容之后每个元素都要重新哈希
    private void resize(){
        Node[] newElem=new Node[this.elem.length*2];
        for (int i = 0; i < this.elem.length; i++) {
            Node cur=this.elem[i];
            while(cur!=null){
                int index= cur.Key%this.elem.length;
                Node newCur=newElem[index];
                if(newCur==null){
                    newElem[index]=cur;
                    cur=cur.next;
                    this.elem[i]=cur;
                    newElem[index].next=null;
                }else {
                    while(newCur.next!=null){
                        newCur=newCur.next;
                    }
                    newCur.next=cur;
                    cur=cur.next;
                    this.elem[i]=cur;
                    newCur.next.next=null;
                }

            }
        }
        this.elem=newElem;
    }

    private double loadFactor(){
            return 1.0*this.useSize/this.elem.length;
    }
    public int get(int key){
        return 0;
    }

    @Override
    public String toString() {
        return "HashTable{" +
                "elem=" + Arrays.toString(elem) +
                ", useSize=" + useSize +
                '}';
    }
}


